package style.Leetcode.初级算法.array.array_20221013_2_子数组最大平均数;

/**
 * 643. 子数组最大平均数 I
 * <p>
 * 给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
 * 请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
 * <p>
 * <p>
 * 示例 1：
 * 输入：nums = [1,12,-5,-6,50,3], k = 4
 * 输出：12.75
 * 解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
 * 示例 2：
 * 输入：nums = [5], k = 1
 * 输出：5.00000
 * <p>
 * 提示：
 * <p>
 * n == nums.length
 * 1 <= k <= n <= 105
 * -104 <= nums[i] <= 104
 */
public class Solution {
    /**
     * 滑动窗口
     *      获取第一个窗口的总和，然后再依次向右移动，每次移动加上右侧减去左侧
     *      判断最大值即可
     */
    public double findMaxAverage(int[] nums, int k) {
        double maxSum = 0.0;
        double sum = 0;

        // 求出第一个窗口的和
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        // 保存第一个窗口的最大值
        maxSum = sum;

        for (int i = k; i < nums.length; i++) {
            sum = sum + nums[i] - nums[i-k];
            maxSum = Math.max(sum, maxSum);
        }
        return maxSum/k;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.findMaxAverage(new int[]{5}, 1));
    }
}
